package com.jml.递归;


 /**
 * @author:jml
 * @date: 2020/3/27 0027 10:09
 * @description：
  * 12345使用子树的概念
  * 1234    5              把1234当做一个整体
  * 123     4    5         把123当做一个整体
  * 12      3    4    5    把12当做一个整体
  *
  * from    inner  to                        from->from + to     inner->from + to    to->inner
  * 1234567
  *把123456看整体，借用to塔座移动到inner        from    to  inner
  * 7       123456
  * 此时剩下7可以直接移动到目的塔座
  *         123456    7
  *把12345看整体，借用to塔座移动到from          to    from  inner
  * 12345     6       7
  *此时剩下6可以直接移动到目的塔座
  * 12345             6,7
  * 把1234看整体，借用to塔座移动到inner         from    to   inner
  * 5       1234      6,7
  * 此时剩下5可以直接移动到目的塔座
  *         1234         5,6,7
  * 把123看整体，借用to塔座移动到from          to    from  inner
  * 123        4         5,6,7
  * 此时剩下4可以直接移动到目的塔座
  * 123                  4,5,6,7
  * 把12看整体，借用to塔座移动到innet           from    to   inner
  * 3          12        4,5,6,7
  * 此时剩下3可以直接移动到目的塔座
  *            12        3,4,5,6,7
  * 把1看整体，借用to塔座移动到from             to    from  inner
  * 1           2        3,4,5,6,7
  * 此时剩下2可以直接移动到目的塔座
  * 1                    2,3,4,5,6,7
  * 此时剩下1可以直接移动到目的塔座
  *                      1,2,3,4,5,6,7
 */
public class 汉诺塔 {

  /**
   *topN：移动盘子的数目
   * from：起始塔座
   * inter：中间塔座
   * to:目标塔座
   */
    public static void doTower(int topN,char from ,char inter,char to){
        if(topN==1){
            System.out.println("盘子1从"+from +"塔座到" + to+"塔座");
        }else{
            //把上面所有的盘子看做一个整体，当场两个盘子来看
            //先移动上面的盘子当做整体，借用to移动到inner
            doTower(topN-1,from,to,inter);
            //只剩下最后一个盘子就直接从from移动到to目的塔座
            System.out.println("盘子" + topN + "从"+from +"塔座到" + to+"塔座");
            //剩下的一个盘子整体直接从inner塔座，借用from，移动到to目的节点
            doTower(topN-1,inter,from,to);
        }
    }

     public static void main(String[] args) {
         doTower(4,'a','b','c');
     }
}
